package sort.past;

import java.util.Arrays;

/**
 * 堆排
 */
public class HeapSort {
    /**
     * 对数组nums进行堆排
     * @param nums
     */
    public static void heapSort(int[] nums) {
        int len = nums.length;
        // 将数组中非叶子通过下沉操作将数组转化为最大堆的形式
        // 从最后一个节点的父节点开始，也就是最后一个非叶子节点开始
        for (int i = (len - 1 - 1) / 2; i >= 0; i--) {
            siftDown(nums, i, len);
        }
        // 不断替换堆顶元素和限制范围内的的最后一个元素，就将当前最大值存到属于它的位置（数组同步操作），然后对堆顶元素进行下沉操作维持一个最大堆便于下次取到最大值
        for (int i = len - 1; i > 0; i--) {
            swap(nums, 0, i);
            siftDown(nums, 0, i);
        }
    }

    /**
     * 对数组nums中，处于i位置的元素进行下沉操作
     * @param nums
     * @param i
     * @param len 限制下沉的范围，范围为0到len - 1
     */
    private static void siftDown(int[] nums, int i, int len) {
        while ((i << 1) + 1 < len) { // 当还有子树
            int k = (i << 1) + 1;
            if (k + 1 < len && nums[k + 1] > nums[k]) {
                k = k + 1;
            }
            if (nums[i] >= nums[k]) {
                // 若节点值大于等于子节点中最大值，则下沉结束
                return;
            }
            swap(nums, i, k);
            i = k;
        }
    }

    /**
     * 将数组nums中处于i位置和处于k位置的值进行交换
     * @param nums
     * @param i
     * @param k
     */
    private static void swap(int[] nums, int i, int k) {
        int tmp = nums[i];
        nums[i] = nums[k];
        nums[k] = tmp;
    }

    public static void main(String[] args) {
        int[] nums = new int[] {3, 4, 2, 7, 6, 1, 9, 5, 8};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
